package com.techyuan.algorithm.questions;

import com.techyuan.algorithm.utils.PrintUtil;

import java.util.Arrays;

/**
 * 线性查找 解决问题
 * @author derek.tian on 2016/11/23.
 */
public class FindMaxinumSubarrayByLA {
    public static void main(String[] args) {
        Integer[] quesList = createQuesList();
        PrintUtil.printArrPretty(quesList, "原始数组:%s");
        MaxinumResult questResult = findMaxinumSubarray(quesList, 0, quesList.length - 1);
        PrintUtil.printArrPretty(Arrays.copyOfRange(quesList, questResult.getLow(), questResult.getHight() + 1), "最大子数组为:%s,子数组和为:" + questResult.getSum());
    }

    /**
     * 查找最大子数组
     *
     * @param qArr
     * @param low
     * @param high
     * @return
     */
    private static MaxinumResult findMaxinumSubarray(Integer[] qArr, int low, int high) {
        MaxinumResult maxinumResult = new MaxinumResult(0, 0, 0);
        long curSum = 0;
        for (int i = low; i <= high; i++) {
            curSum = curSum + qArr[i];
            if (curSum > maxinumResult.getSum()) {
                maxinumResult.setSum(curSum);
                maxinumResult.setHight(i);//更新终点
            }

            if (curSum < 0) {
                curSum = 0;
                maxinumResult.setLow(i + 1 > high ? maxinumResult.getLow() : i + 1);//设置起点
            }
        }

        return maxinumResult;
    }

    /**
     * 创建问题数组
     *
     * @return
     */
    private static Integer[] createQuesList() {
        //return new Integer[]{2, 4, -7, 5, 2, -1, 2, -4, 3};
        return new Integer[]{-1, 2, 3, -8, -9, 19};
    }

    private static class MaxinumResult {
        public MaxinumResult() {
        }

        public MaxinumResult(int l, int h, long sum) {
            this.low = l;
            this.hight = h;
            this.sum = sum;
        }

        private int low;
        private int hight;
        private long sum;

        public void setLow(int low) {
            this.low = low;
        }

        public int getLow() {
            return low;
        }

        public void setHight(int hight) {
            this.hight = hight;
        }

        public int getHight() {
            return hight;
        }

        public long getSum() {
            return sum;
        }

        public void setSum(long sum) {
            this.sum = sum;
        }
    }
}
